%----------------------
%      集合论
%----------------------

%\chapter{集合论(set theory)}

\section{集合(set)}

\subsection{基本概念}

\begin{definition}{集合(Set)}{int}
	具有共同性质的一些事物汇集成一个集体，就形成\textbf{集合}。这些事物称为集合的\textbf{元素}或\textbf{成员}。
\end{definition}

通常用大写字母表示集合(如：A，B，C)，用小写字母（如：a，b，c）表示元素。
如何集合由有限个元素组成，此集合称为有限集，否则称为无限集。
集合的表示方法通常有两种：

\begin{enumerate}[noitemsep]
	\item 列举法:${1,2,3},{1,2,3,4,5,6.\ldots}$；
	\item 叙述法:${x \mid x^2 -1 =0},{x \mid x > 60}$；
\end{enumerate}

下面用SageMath \footnote{SageMath是一个开源的数学计算软件} 来进行集合定义方式的示例。

\begin{SageMath}{罗列方式定义有限集合} 
	\begin{verbatim}
	sage: #有限集的定义：罗列的方式
	....: x=Set([1,2,3,4,5,6])
	....: x
	....: x.is_finite()
	....: 
	{1, 2, 3, 4, 5, 6}
	True
	\end{verbatim}
\end{SageMath}


\begin{SageMath}{描述方式定义有限集合}
	\begin{verbatim}
	sage: #有限集的定义：描述的方式
	....: x=range(0,10)
	....: type(x) 
	....: #可以看到这时的x是list类型，并非是set
	....: x=Set(x)
	....: x
	....: #可以看出其已经转换为一个set
	....: 
	<type 'list'>
	{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	\end{verbatim}
\end{SageMath}
	
\begin{SageMath}{无限集合定义}
	\begin{verbatim}
	sage: #定义一个无限集:是一种描述方式，interpreter
	....: x=R(1,5)
	....: x
	....: #R Interpreter
	....: 2 in x
	....: #True
	....: 2.1 in x
	....: 2.111111 in x
	....: 
	R Interpreter
	True
	True
	True
	\end{verbatim}
\end{SageMath}



\subsection{集合之间的关系}

有了集合的定义，下面我们要展开对集合的研究，对于一个事物的研究，可以从两个大的方面展开，一个是研究其自身的构成，这是向内的方向，另外一个是研究其于周边个体的关系，这是向外的方向，下面我们就从向外的方向看看记着之间有什么样的关系。

\begin{definition}{包含(contain)}{int}
	A包含于B, 或B包含A
	$\stackrel{Def}{\longleftrightarrow}$
	$A \subseteq B \Leftrightarrow(\forall x)(x \in A \rightarrow x \in B)$
\end{definition}

\begin{definition}{真子集(real subset)}{int}
	A为B的真子集
	$\stackrel{Def}{\longleftrightarrow}$
	$A \subset B \Leftrightarrow(\forall x)(x \in A \rightarrow x \in B) \wedge(\exists x)(x \in B \wedge x \notin A)$
\end{definition}

\begin{definition}{相等(equal)}{int}
	A和B相等
	$\stackrel{Def}{\longleftrightarrow}$
	$A=B \Leftrightarrow A \subseteq B \wedge B \subseteq A$
\end{definition}

\subsection{特殊集合}

看完集合之间的关系，下面我们看看一些特殊的集合。

\begin{definition}{空集(empty set)}{int}
	不含任何元素的集合称为空集。形式化表示为
	$\emptyset=\{x | p(x) \wedge \sim p(x)\}$
	其中p表示任意谓词，~表示否。
\end{definition}

\begin{definition}{幂集(power set)}{int}
	给定集合A，由集合A的所有子集组成的集合称为集合A的幂集，记为$\rho\left( A\right) $或$2^A$,即$\rho(A)=\{B | B \subseteq A\}$。
\end{definition}

\begin{example}\\
	$A = \left\lbrace1,2,3\right\rbrace $，求集合A的幂集。
\end{example}

\begin{solution}
	$\rho (A)=\left\lbrace \varPhi,A,\left\lbrace 1 \right\rbrace ,\left\lbrace 2\right\rbrace ,\left\lbrace 3\right\rbrace ,\left\lbrace 1,2\right\rbrace ,\left\lbrace 1,3\right\rbrace ,\left\lbrace 2,3\right\rbrace \right\rbrace $
\end{solution}

\begin{definition}{全集(universal set)}{int}
	在一定范围内，如果所有的集合均为某一个集合的子集，则称该集合为全集，记为E。
\end{definition}

\begin{tcolorbox}[title = {思考}]
	以上定义中的一定范围是指的什么？你研究的或者界定的。
	\tcblower
	全集的形式化表述是什么？$ E= \left\lbrace x \mid p(x) \vee \sim p(x) \right\rbrace  $
  \end{tcolorbox}

\begin{tcolorbox}[title = {思考}]
	定义完基本对象了(此处为集合)，对象之间的关系(或称为运算)需要接着定义。
	
\end{tcolorbox}

\subsection{集合运算}

\begin{definition}{基本运算(operation)}{int}
	\begin{enumerate}[noitemsep]
		\item 交集(Intersection)：$A \cap B=\{x | x \in A \wedge x \in B\}$。
		
		\item 并集(Union)：$A \cup B=\{x | x \in A \vee x \in B\}$。
		
		\item 补集（或者成为“差”）(Difference)：$A-B=\{x \in A \wedge x \notin B\}=\{x | x \in A \wedge(x \notin B)\}$。
		
		\item 绝对补(absolute complement)：设E为全集, 对任一集合A关于E的补集E-A, 称为集合A的绝对补，$\sim A=E-A=\{x | x \in E \wedge x \notin A\}$。
		
		\item 对称差(Symmetric Difference)：A和B的对称差为集合S，$S=A \oplus B=(A-B) \cup(B-A)=\{x |(x \in A \wedge x \notin B) \vee(x \in B \wedge x \notin A)\} \}$。
	\end{enumerate}	
\end{definition}

\begin{SageMath}{基本运算}
	\begin{verbatim}
		sage: a=Set([1,2,3,4,5,6])
		....: b=Set([0,1,2])
		....: c=union(a,b)
		....: c
		....: c=a.intersection(b)
		....: c
		....: c=a.difference(b)
		....: c
		....: c=a.symmetric_difference(b)
		....: c
		....:
		[0, 1, 2, 3, 4, 5, 6]
		{1, 2}
		{3, 4, 5, 6}
		{0, 3, 4, 5, 6}
	\end{verbatim}
\end{SageMath}

\begin{theorem}{空集性质}{set} 
	（1）  对于任意集合A，$\emptyset \subseteq A$。
	（2）  空集是唯一的。
\end{theorem}
\begin{proof}
	(1) 假设结论不成立，那么至少存在一个元素属于空集，但不属于A，按照空集的定义，显然任何元素都不属于空集，所以产生矛盾，故假设错误，结论得证。\\
	(2) 反证法：假设有两个不同的空集$\phi_1, \phi_2$，根据空集性质$\phi_1 \subseteq \phi_2$，$\phi_2 \subseteq \phi_1$，根据集合相等的定义，我们知道这两个集合相等，与假设矛盾，结论得证。
\end{proof}




\begin{theorem}{运算律(Algorithm,Operational Law)}{set} 
	\begin{enumerate}[noitemsep]
		\item 幂等律\\
				$A \cup A=A$\\
				$A \cap A=A$\\
		\item 交换律\\
			$\begin{aligned} A \cup B &=B \cup A \\ A \cap B &=B \cap A \\ A \oplus B &=B \oplus A \end{aligned}$\\
		\item 结合律\\
			$(A \cup B) \cup C=A \cup(B \cup C)$\\
			$(A \cap B) \cap C=A \cap(B \cap C)$\\
			$(A \oplus B) \oplus C=A \oplus(B \oplus C)$\\
		\item 分配律\\
			$\begin{aligned} A \cup(B \cap C) &=(A \cup B) \cap(A \cup C) \\ A \cap(B \cup C) &=(A \cap B) \cup(A \cap C) \\ A \cap(B-C) &=(A \cap B)-(A \cap C) \end{aligned}$
		\item 同一律\\
			$\begin{aligned} A \cup \emptyset &=A \\ A \cap E &=A \\ A-\emptyset &=A \\ A \oplus \emptyset &=A \end{aligned}$\\
		\item 零律\\
			$A \cup E=E$\\
			$A \cap \emptyset=\emptyset$\\
		\item 互补律\\
			$A \cup \sim A=E$\\
			$A \cap \sim A=\emptyset$\\
			$\sim E=\emptyset$\\
			$\sim \emptyset=E$\\
		\item 吸收律\\
			$A \cup(A \cap B)=A$\\
			$A \cap(A \cup B)=A$\\
		\item 摩根定律\\
			$\begin{aligned} 
				\sim(A \cup B) &=\sim A \cap \sim B \\ 
				\sim(A \cap B) &=\sim A \cup \sim B \\ 
				A-(B \cup C) &=(A-B) \cap(A-C) \\ 
				A-(B \cap C) &=(A-B) \cup(A-C) \\
			\end{aligned}$
		\item 双重否定律\\
			$\sim(\sim A)=A$\\
		\item 其他\\
			$A \oplus A=\emptyset$\\
			$A-A=\emptyset$\\
			$A \cap B \subseteq A$\\
			$A \cap B \subseteq B$\\
			$A \subseteq A \cup B$\\
			$B \subseteq A \cup B$\\
			$A-B \subseteq A$\\
			$A-B=A \cap \sim B$\\
			$A \oplus B=(A-B) \cup(B-A)=(A \cup B)-(A \cap B)=(A \cap B) \cup(\sim A \cap B)$\\
	
	\end{enumerate}	
\end{theorem}

\begin{note}
	文氏图(Venn Diagram)用来表示集合间的运算很直观，便于理解。

\end{note}

\begin{example}\\
	$A-B=A \cap \sim B$
\end{example}
\begin{proof}
	$A-B=\left\lbrace x \mid x \in A \cap x \notin B \right\rbrace = \left\lbrace x \mid x \in A\right\rbrace \cap \left\lbrace x \mid x \notin B \right\rbrace =A \cap \sim B$
\end{proof}

\begin{example}\\
	证明幂等律$A \cup A=A$。
\end{example}
	
\begin{proof}
	对于$A \cup A$ 中任意一个元素x，有：\\
	$x \in A \cup A \Leftrightarrow x\in A \vee x \in A \Leftrightarrow x \in A$
	，根据集合相等的定义，$A \cup A=A$成立。
\end{proof}

\subsection{集合的划分}

\begin{definition}{集合的一个划分(partition)}{int}
	集合$S_1,S_2,\dots,S_m$是集合S的子集，且$S=S_1 \cup S_2 \cup \dots \cup S_m,S_i \cap S_j=\emptyset,i\neq j$，则称$S_1,S_2,\dots,S_m$是S的一个划分。
\end{definition}

\begin{theorem}{划分的加法原理}{set}
	设$S_1,S_2,\dots,S_m$是集合S的一个划分，则$|S|=|S_1|+ |S_2|+ \dots + |S_m|$。
\end{theorem}

\begin{theorem}{划分的乘法原理}{set}
	设$S_1,S_2,\dots,S_m$是m个有限集，则$|S_1\times S_2 \times \dots \times S_m| = |S_1| \cdot |S_2| \cdot \dots \cdot |S_m|$。
\end{theorem}

\begin{theorem}{划分的减法原理}{set}
	设E为全集，则$|A| = |E| - |E-A|$。
\end{theorem}

\begin{theorem}{划分的除法原理}{set}
	设S为有限集合，它被划分为m个部分($S_1,S_2,\dots,S_m$)，且每个部分所包含元素数量相同($|S_1|=|S_2|=\dots=|S_m|$)，则：\\
	$m=\dfrac{|S|}{|S_i|},i=1,2,\dots,m$
\end{theorem}

\section{关系(relation)}

\subsection{序偶和n元组}

\begin{definition}{序偶(ordered couple)}{int}
由两个具有给定次序的个体x和y(允许x = y)所组成的序列, 称为序偶, 记作<x,y>. 其中x称为第一分量, y称为第二分量。
\end{definition}

\begin{definition}{序偶相等}{int}
设<a,b>,<x,y>是两个序偶, 则<a,b> <x,y>当且仅当a = x且b = y.
\end{definition}

\begin{definition}{有序n元组(Ordered n-tuple)}{int}
由n个具有给定次序的个体$a_1,a_2,\cdots,a_n$组成的序列, 称为有序n元组, 记作
$\left\langle  a_1,a_2,\cdots,a_n \right\rangle$ 。
\end{definition}

\subsection{笛卡尔积}
\subsubsection{基本概念}
\begin{definition}{笛卡儿积(Cartesian product)}{int}
设$A_1,A_2,…,A_n$是任意给定的n个集合, 若有序n元组$<a_1,a_2,…,a_n>$的第一个分量是取自集合$A_1$里的元素, 第二个分量是取自集合$A_2$里的元素, …, 第n个分量是取自集合$A_n$里的元素, 则由所有这样的有序n元组所组成的集合称为集合$A_1,A_2,…,A_n$的笛卡儿积, 并用$A_1 \times A_2 \times … \times A_n$表示, 即
$A_{1} \times A_{2} \times \cdots \times A_{n}=\left\{<a_{1}, a_{2}, \dots, a_{n}>| a_{i} \in A_{i}, i=1,2, \dots, n\right\}$。
\end{definition}
\begin{note}
	笛卡尔积是一种特殊集合，什么是“特殊”？所谓特殊是具有某种特点的一类集合。特点是从特定视角，也就是从某个观测点所看到他们不同于其他的区别。
\end{note}

\begin{example}\\
	$A={a,b},B={0,1,2}$,求$A \times B$和$B \times A$.
\end{example}
\begin{solution}
	$A \times B = { <a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2> }$\\
	$B \times A = { <0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b> }$
\end{solution}

\subsubsection{笛卡尔积运算律}
\begin{theorem}{笛卡尔积性质}{set}
	\begin{enumerate}[noitemsep]
		\item 交换律不成立, 即$A \times B \neq B \times A$。
		\item 结合律不成立, 即$(A \times B) \times C \neq A \times(B \times C)$。
		\item 下列分配律是成立:\\
		$\begin{aligned} 
			A \times(B \cup C) &=(A \times B) \cup(A \times C) \\ 
			A \times(B \cap C) &=(A \times B) \cap(A \times C) \\
			(A \cup B) \times C &=(A \times C) \cup(B \times C) \\
			(A \cap B) \times C &=(A \times C) \cap(B \times C) \\ 
			A \times(B-C) &=(A \times B)-(A \times C) \\
			(A-B) \times C &=(A \times C)-(B \times C) 
		\end{aligned}$
		\item 若$C \neq \emptyset$, 则
		$A \subseteq B \Leftrightarrow(A \times C \subseteq B \times C) \Leftrightarrow(C \times A \subseteq C \times B)$。
		\item 设A,B,C,D是四个非空集合,
		$A \times B \subseteq C \times D \Leftrightarrow A \subseteq C \& B \subseteq D$
	\end{enumerate}
\end{theorem}
\begin{example}\\
	证明$(A \oplus B) \times C =(A \times C)\oplus(B \times C)$.
\end{example}
\begin{proof}
	$(A \oplus B) \times C \\
	=((A-B) \cup (B-A)) \times C \\
	=(A-B) \times C \cup (B-A) \times C \\
	=((A \times C)-(B \times C)) \cup ((B \times C)-(A \times C)) \\
	=(A \times C)\oplus(B \times C)$
\end{proof}

\subsection{关系}
\subsubsection{基本概念}
\begin{definition}{n元关系(n-ary relation)}{int}
	设$A_1,A_2, \dots ,A_n$是任意给定的集合, 笛卡儿积$A_1\times A_2 \times \dots \times A_n$ 的任何一个子集R称为$A_1,A_2, \dots ,A_n$上的一个n元关系。
\end{definition}
其实关系的本质仍然是一个集合。\par
\begin{note}
	为什么是笛卡尔积的一个子集？以笛卡尔二维坐标为例来思考关系的定义。X，Y如果分别是两个实数集合，他俩的笛卡尔积可以组成整个二维空间，平面上的一条直线就是一个关系。
\end{note}
\begin{definition}{二元关系(Binary Relation)}{int}
	A,B是任意两个集合, 则笛卡儿积$A\times B$的任意一个子集R称为从集合A到集合B的一个二元关系, $\left< a,b \right> \in R$也可表示为aRb . 如果一个二元关系是从集合A到其自身的关系，则这样的二元关系称为集合A上的关系。
\end{definition}
\begin{note}
	关系的本质仍为集合。
\end{note}
\begin{example}\\
	我们定义三个集合，A为全中国所有大学，B为所有中国人，$A \times B$是A，B的笛卡尔积，而联大女生显然是其一个子集，也就是说联大女生是A，B上的一个二元关系。
\end{example}

对于二元关系，除了用序偶集合表示外，还可以用矩阵表示，通常也称为关系矩阵。
$A=\left\{a_{1}, a_{2}, \dots, a_{m}\right\}, \quad B=\left\{b_{1}, b_{2}, \dots, b_{n}\right\}$,R为A到B的一个二元关系，则此二元关系R的关系矩阵$M_{R}=\left[r_{i j}\right]_{m \times n}$其中：\\
\begin{equation}
	r_{i j}=\begin{cases}
		1,  \left\langle  a_i,b_j \right\rangle  \in R\\
		0,  \left\langle < a_i,b_j \right\rangle  \notin  R
	\end{cases}
	(i=1,2, \ldots, m ; j=1,2, \dots, n)
\end{equation}

\begin{note}
	(1)概念的表达。\\
	(2)表达方式：比如一个集合，可以表达为$A={1,2,3}$,同样是这个集合在C语言中的表达方式会发生变化。体会同一概念在不同层次和体系或语境或上下文中的表达方式的不同。
\end{note}

\begin{definition}{定义域(Domain)和与值域(range)}{int}
	设R是从集合A到集合B的二元关系，则R中所有序偶的第一个分量组成的集合称为关系R的定义域，记得D(R)，由R中所有序偶的第二个分量组成的集合称为关系R的值域，记作V(R)，即：\\
	$D(R) = \left\lbrace a \mid a \in A \wedge (\exists b)(<a,b> \in R) \right\rbrace $,\\
	$V(R) = \left\lbrace b \mid b \in B \wedge (\exists a)(<a,b> \in R) \right\rbrace $.
\end{definition}
	\begin{example}\\
		$A=\left\lbrace 0,1\right\rbrace ,B=\left\lbrace 0,1\right\rbrace$.\\
		$A \times B=\left\lbrace \left\langle 0,0\right\rangle ,\left\langle 0,1 \right\rangle,\left\langle 1,0\right\rangle , \left\langle 1,1\right\rangle  \right\rbrace ;$\\
		关系$R_1 =\left\lbrace \left\langle 0,0\right\rangle ,\left\langle 1,1 \right\rangle \right\rbrace , R_1 \subset A \times B.$\\
		$R_2 =\left\lbrace \left\langle 0,1\right\rangle ,\left\langle 1,0 \right\rangle \right\rbrace , R_2 \subset A \times B.$\\
		关系$R_1,R_2$的矩阵表示：\\
		$M_{R_1}=\begin{vmatrix}
			1 & 0\\0 &1
		\end{vmatrix},M_{R_2}=\begin{vmatrix}
		0 & 1\\1 &0
		\end{vmatrix}$
	\end{example}

\subsubsection{特殊关系}
	\begin{definition}{空关系(empty relation)与全域关系(universal relation)}{int}
		设R是从集合A到集合B的一个二元关系，若$R=\emptyset$，则称R为空关系，若R=A $\times$ B，则称R为全域关系。
	\end{definition}

	\begin{definition}{恒等关系(identity relation)}{int}
		设$I_X$是从集合X上的一个二元关系，若$I_X=\left\lbrace<x,x> \mid x\in X \right\rbrace $，则称R为恒等关系。
	\end{definition}
\begin{note}
	空关系、全域关系和恒等关系是唯一的。
\end{note}
	\begin{definition}{自反关系(reflexive relation)}{int}
		R在X上自反$\Longleftrightarrow \forall x,x \in X\longrightarrow xRx$。
	\end{definition}
有一些特殊关系具有一些特殊性质，下面我们讨论一些特殊的关系。
	\begin{definition}{反自反关系(anti-reflexive relation)}{int}
		R在X上反自反$\Longleftrightarrow \forall x,x \notin X\longrightarrow xRx$。
	\end{definition}

	\begin{definition}{对称关系(symmetrical relation)}{int}
		R在X上对称$\Longleftrightarrow \forall x \forall y,x \in X \wedge y \in X \wedge xRy\longrightarrow yRx$。
	\end{definition}

	\begin{definition}{反对称关系(antisymmetric relation)}{int}
		R在X上反对称$\Longleftrightarrow \forall x \forall y,x \in X \wedge y \in X \wedge xRy \wedge yRx\longrightarrow y=x$。
	\end{definition}

	\begin{definition}{传递关系(transitive relation)}{int}
		R在X上传递$\Longleftrightarrow \forall x \forall y \forall z,x \in X \wedge y \in X \wedge z \in X \wedge xRy \wedge yRz\longrightarrow xRz$。
	\end{definition}

	\begin{definition}{等价关系(equivalence relation)}{int}
		设R是集合X上的\textbf{二元关系}，若R是\textbf{自反、对称和传递}的，则称R为X上的\textbf{等价关系}。
	\end{definition}

\subsubsection{关系运算}
	\begin{definition}{复合关系(composite relation)}{int}
		设R为X到Y的二元关系，S为Y到Z的二元关系，则$S\circ R$称为R和S的复合关系。也可写为：\\
		$S \circ R=\left\lbrace <x,z> \mid x \in X \wedge z \in Z \wedge (\exists y,y \in Y \wedge <x,y> \in R \wedge <y,z>\in S)\right\rbrace $
	\end{definition}
	关系的复合运算或者合成运算就是求复合关系。复合运算是关系的二元运算，可以由两个关系生成一个新的关系。\newline
	复合关系运算顺序是从右到左。\\
	\begin{example}\\
		R表示父子关系，$R \circ R$生成一个新的关系，新生成的关系是“祖孙关系”。\par
		设B表示兄弟关系，$R \circ B$是叔侄关系，$B \circ R$是父子关系。
	\end{example}
	
	\begin{theorem}{关系复合运算的性质}{set}
		\begin{enumerate}
			\item 满足结合律，$P \circ (S \circ R)=(P \circ S) \circ R $。
			\item 不满足交换律，$R \circ S \neq S \circ R$。
			\item 并元素满足分配率, $P \circ (S \cup R)=(P \circ S) \cup (P \circ R)$ \\
				$(P \cup S) \circ R=(P \circ R) \cup (S\circ R)$
			\item 符合运算对交运算满足包含关系,$R \circ (S \cup P)\subseteq (R\circ S)\cup (R \circ P)$\\
				$(S \cap P)\circ R \subseteq (S \circ R) \cap (P \circ R)$
			\item 设R是X到Y的关系，$I_X$是X中的恒等关系，$I_Y$是Y中的恒等关系，则$I_X \circ R = R \circ I_Y = R$。
		\end{enumerate}
	\end{theorem}
	
	\begin{definition}{关系的n次幂(power)}{int}
		设R是集合A上的二元关系，n为自然数，则R的n次幂记为$R^{n}$，定义为：\\
		(1)  $R^{0}=I_A$;\\
		(2)  $R^{n+1}=R^{n}\circ R$;
	\end{definition}

\begin{example}\\
	$X=\left\lbrace 0,1 \right\rbrace $,X的二元关系$R_1=\left\lbrace \left\langle 1,1\right\rangle \right\rbrace $,$R_2=\left\lbrace \left\langle 0,1\right\rangle ,\left\langle 1,0\right\rangle \right\rbrace $，分别求$R_1,R_2$各次幂。
\end{example}
\begin{solution}
	$R_1^0 = I_X=\left\lbrace \left\langle 0,0 \right\rangle ,\left\langle 1,1 \right\rangle \right\rbrace $\\
	$R_1^1 = R_1=\left\lbrace \left\langle 1,1 \right\rangle \right\rbrace $\\
	$R_1^2 = R_1 \circ R_1=R_1=\left\lbrace \left\langle 1,1 \right\rangle \right\rbrace = R_1 $\\
	$R_1^2 = R_1$\\
	\ldots \\
	$R_2^0 = I_X=\left\lbrace \left\langle 0,0 \right\rangle ,\left\langle 1,1 \right\rangle \right\rbrace $\\
	$R_2^1 = R_2=\left\lbrace \left\langle 0,1\right\rangle ,\left\langle 1,0\right\rangle \right\rbrace $\\
	$R_2^2 = R_2 \circ R_2 = I_X$\\
	$R_2^3 = R_2 \circ R_2^2 =R_2$\\
	$R_2^4 = R_2 \circ R_2^3 =I_X$\\
\end{solution}
	\begin{theorem}{幂运算性质}{int}
		设R是集合X中的二元关系，$m,n \in N$，则：\\
		(1)  $R^{m} \circ R^{n}=R^{m+n}$;\\
		(2)  $(R^{m})^{n} = R^{m \times n}$.
	\end{theorem}
	\begin{proof}
		数学归纳法\\
		当$n=0$时，$R^m \circ R^n = R^m \circ R^0 = R^m \circ I_X = R^m=R^{m+0}=R^{m+n}$.\\
		假设$n=k$时，$R^m \circ R^k =R^{m+k}$.\\
		当$n=k+1$时，$R^m \circ R^{k+1} = R^m \circ \left) R \circ R^k \right( =R^m \circ \left) R^k \circ R \right( 
		= \left) R^m \circ R^k \right(  \circ R = R^{m+k} \circ R = R ^{m+k+1}$.\\
		由上可知，对于所有$m,n \in \mathbb{N} $.
		
	\end{proof}
	\begin{definition}{逆关系(inverse relation)}{int}
		设R是X到Y的二元关系，若将R中的每一个序偶的元素顺序互换，所得到的集合称为R的逆关系，记做$R^{c}$。即：\\
		$R^{c}=\left\lbrace <y,x> \mid <x,y> \in R\right\rbrace $。
	\end{definition}
	
	\begin{note}
		任何一个二元关系的逆关系总是存在的。
	\end{note}
	\begin{theorem}{逆运算性质}{int}
		设$R_1,R_2,R_3$都是从A到B的二元关系，则下列等式成立：\\
		(1)  $(R_1 \cup R_2)^{c} = R_1^{c} \cup R_2^{c}$;\\
		(2)  $(R_1\cap R_2)^{c} = R_1^{c} \cap R_2^{c}$;\\
		(3)  $(A \times B)^{c} =B \times A$;\\
		(4)  $(\bar{R})^{c}=\bar{R^{c}}$，也可以记为$(\sim R)^{c}=~\sim R^{c}$;\\
		(5)  $(R_1-R_2)^{c}=R_1^{c}-R_2^{c}$。
	\end{theorem}

\begin{example}\\
	证明$(R_1 \cup R_2)^{c} = R_1^{c} \cup R_2^{c}$.
\end{example}
\begin{proof}
	$\left\langle x,y \right\rangle \in \left( R_1 \cup R_2  \right) ^c \Rightarrow $ \\
	$\left\langle y,x \right\rangle \in R_1 \cup R_2  \Rightarrow$\\
	$\left\langle y,x \right\rangle \in R_1 \vee \left\langle y,x \right\rangle \in R_2 \Rightarrow $\\
	$\left\langle x,y \right\rangle \in R_1^c \vee \left\langle x,y \right\rangle \in R_2^c \Rightarrow $\\
	$\left\langle x,y \right\rangle \in R_1^{c} \cup R_2^{c}$.
\end{proof}

\section{函数(function)}

\subsection{定义}
在所有关系中有一类特殊二元关系，这类关系定义域和值域有特殊的对应关系。下面我们讨论这种特殊的关系。

\begin{definition}{函数(function)/ 映射(mapping)}{int}
	f是任意两个集合X到Y的一个关系，若对于$\forall x \in X$，都有唯一的$y \in Y$，使得$<x,y> \in f$，则称关系f为函数，记做$f:X\rightarrow Y$或$X\xrightarrow{f} Y$。x称为自变元，y称为在f作用下x的像，也可记为$y=f(x)$。函数也称为映射。
\end{definition}

\begin{note}
	关系是笛卡尔积的一个子集，而这个子集再加上一定约束就是函数。而这个约束就是对于定义域中的任何一个元素$x_0$，有且只存在一个形如$<x_0,*>$的序偶。
\end{note}

\begin{example}\\
	$X=\left\lbrace 1,2,3,4\right\rbrace , Y=\left\lbrace a,b,c,d \right\rbrace $,下列哪些关系是函数。\\
	$f_1=\left\lbrace \left\langle 1,a\right\rangle , \left\langle 2,c\right\rangle, \left\langle 3,b\right\rangle , \left\langle 4,d\right\rangle \right\rbrace $\\
	$f_2=\left\lbrace \left\langle 1,a\right\rangle , \left\langle 2,b\right\rangle, \left\langle 3,d\right\rangle , \left\langle 4,b\right\rangle \right\rbrace $\\
	$f_3=\left\lbrace \left\langle 1,a\right\rangle , \left\langle 3,b\right\rangle , \left\langle 4,d\right\rangle \right\rbrace $\\
	$f_4=\left\lbrace \left\langle 1,a\right\rangle , \left\langle 1,b\right\rangle, \left\langle 2,b\right\rangle , \left\langle 3,c\right\rangle , \left\langle 4,d\right\rangle \right\rbrace $\\
\end{example}
\begin{solution}
	$f_1,f_2$是函数。$f_3$不是函数，因为$f_3 \left(  x \right) \notin Y$。$f_4$不是函数，因为$f_4 \left( 1 \right) $对应两个Y中元素。
\end{solution}

\subsection{函数间关系}

\begin{definition}{函数相等}{int}
	f，g都是从A到B的函数，若他们有相同的定义域和值域，并且$\forall x \in A$都有$f(x)=g(x)$，则称函数f和g相等，记为$f=g$。
\end{definition}

\subsection{特殊的函数}
\begin{definition}{满射(surjection)}{int}
	$X\xrightarrow{f} Y$，如果Y中的每一个元素都是X中的一个或者多个元素的像，则称这个映射是满射。
\end{definition}

\begin{note}
	满射我们也可以这样来描述，就是值域中的每个元素y都有对应的x存在，使得$f(x)=y$。
\end{note}

\begin{definition}{单射(injective)}{int}
	从X到Y的映射中，若X中没有两个元素有相同的像，则称这个映射为单射。
\end{definition}

\begin{definition}{双射(Bijection)}{int}
	从X到Y的映射中，若既是满射又是单射，称这个映射为双射，也称这样的映射是一一映射或一一对应。
\end{definition}

\begin{definition}{常函数(constant function)}{int}
	f称为常函数$\Longleftrightarrow \exists y_0 \in Y,\forall x \in X,f(x)=y_0$。
\end{definition}

\begin{definition}{恒等函数(identity$\footnote{an equation that is satisfied for all values of the symbols}$ function)}{int}
	如果$I_X={<x,x> \mid x \in X}$，则称$I_X=X\rightarrow X$为恒等函数。
\end{definition}


\begin{theorem}{}{set}
	X和Y为有限集，且X和Y的元素个数相同(记为$|X|=|Y|$)，则$f:X\rightarrow Y$是单射，当且仅当它是一个满射。
\end{theorem}
\begin{proof}
	(1)若f是单射，则$|X| = |f(X)|$,已知$|X|=|Y|$,所以$|Y| = |f(X)|$,因为Y是有限集,因此f是满射。\\
	(2)若f是满射，则$|Y| = |f(X)|$,已知$|X|=|Y|$,所以$|X| = |f(X)|$,因为X是有限集。因此f是单射。
\end{proof}
以上这个定理只有在有限集时才成立，在无限集上不一定成立，如$f:\mathbb{I} \rightarrow \mathbb{I}$,f(x)=2x，这是将整数映射为偶整数的，显然这是一个单射，单不是满射。
\begin{theorem}{}{set}
	设$f:X\rightarrow Y$是一个双射函数，那么$f^{c}$是$Y \rightarrow X$的双射函数。
\end{theorem}


\subsection{函数的运算}
\begin{definition}{逆函数/反函数(Inverse Function)}{int}
	设$f:X\rightarrow Y$是一个双射函数，称$Y\rightarrow X$的双射函数$f^{c}$为f的逆函数，记作$f^{-1}$。
\end{definition}

\begin{definition}{左边可复合(composite)}{int}
	$f:X\rightarrow Y,g:W\rightarrow Z$，若$f(X) \subseteq W $(或$Y \subseteq W$)，则$g \circ f = {<x,z> \mid x \in X \wedge z \in Z \wedge \exists y(y \in Y \wedge y=f(x) \wedge z=g(y))}$，称g在函数f的左边可复合。
\end{definition}
\begin{note}
	复合运算的顺序是从右向左。
\end{note}

\begin{theorem}{}{set}
	两个函数的复合是一个函数。
\end{theorem}

\begin{theorem}{}{set}
	令$g \circ f$是一个复合函数。\\
	(1)  若g和f是满射，则$g \circ f$是满射。\\
	(2)  若g和f是单射，则$g \circ f$是单射。\\
	(3)  若g和f是双射，则$g \circ f$是双射。
\end{theorem}

\begin{theorem}{}{set}
	$f:X\rightarrow Y \Rightarrow f=f \circ I_X=I_Y \circ f$。
\end{theorem}

\begin{theorem}{}{set}
	$f:X\rightarrow Y$是双射$\Rightarrow (f^{-1})^{-1}=f$。
\end{theorem}

\begin{theorem}{}{set}
	$f:X\rightarrow Y,g:Y\rightarrow Z$都是双射$\Rightarrow (g\circ f)^{-1}=f^{-1} \circ g^{-1}$。
\end{theorem}


\section{势(potential)}

\begin{definition}{集合等势(equivalent set)}{int}
	当且仅当集合A和B之间存在一一对应的函数，集合A与集合B称为等势，记作$A \sim B$。
\end{definition}
\begin{note}
	集合等势和集合中元素个数相同是一个概念吗？\par
	显然不是。
\end{note}
\begin{example}
	证明区间$[0,1]$和$(0,1)$等势。
\end{example}
\begin{proof}
	设集合$A={0,1,\frac{1}{2},\ldots,\frac{1}{n},\ldots}$，显然$A \subseteq [0,1]$,定义$f:[0,1] \rightarrow(0,1)$，使得\\
	$$f(x)=
	\begin{cases}
	\frac{1}{2}& x=0\\
	\frac{1}{3}& x=1\\
	\frac{1}{\frac{1}{x}+2}& x \in {\frac{1}{2},\frac{1}{3},\ldots,\frac{1}{n},\ldots} \\
	x& x \in (0,1)-A
	\end{cases}$$
	可知f是个双射函数，命题得证。
\end{proof}
\begin{definition}{有限集合与无限集合，可数集或可列集(finite set, infinite set,countable set)}{int}
	如果存在一个从集合${0,1,\dots,n-1}$到集合A的双射，那么称集合A是有限的，如果A不是有限的，那么称A为无限的。若有从正整数集合${1,2,\dots,n,\dots}$到A的双射，则称A是可数集或可列集。
\end{definition}

\begin{theorem}{}{set}
	在集合族上等势关系是一个等价关系。
\end{theorem}

\begin{theorem}{}{set}
	自然数、正奇数、正偶数、整数集是可数集。
\end{theorem}

\section{皮亚诺算术公理系统}

\begin{definition}{后继集(follow set)}{int}
	给定集合A，集合A的后继集记为$A^+ \Leftrightarrow A \cup \left\lbrace A \right\rbrace $。
\end{definition}

\begin{note}
	后继集也称为集合的后继(successor of a set)，是集合的一种一元运算，亦称为后继运算，或后继函数。
\end{note}
\begin{example}\\
	对于空集$ \varPhi $,$\varPhi  \triangleq 0$,$ \varPhi $的后继集 $\varPhi ^+ = 0^+= \varPhi \cup \left\lbrace \varPhi \right\rbrace = \left\lbrace \varPhi \right\rbrace  \triangleq 1$\\
	$1^+ = \left\lbrace  \varPhi, \left\lbrace  \varPhi \right\rbrace  \right\rbrace  \triangleq 2$
\end{example}

皮亚诺公理是意大利皮亚诺所构造的算术公理系统中的公理。1889年，在数学家戴德金工作的基础上，皮亚诺在《用一种新方法陈述的算术原理》一书中提出了一个算术公理系统，这个公理系统有九条公理，其中四条是关于“相等”的，五条是刻画数的，并且以l而不是0作为基本概念。在后来的著作中，皮亚诺对这一算术系统作了修改，去除了关于“相等”的四条公理，并且以0取代1作为基本概念，构造了沿用至今的皮亚诺算术公理系统。
\footnote{此段描述来自于
	%\begin{verbatim}
	https://baike.baidu.com/item/\%E7\%9A\%AE\%E4\%BA\%9A\%E8\%AF\%BA\%E5\%85\%AC\%E7\%90\%86，在原链接的描述总，此段话引自：彭漪涟．逻辑学大辞典：上海辞书出版社，2004年12月
	%\end{verbatim} 
}
\par

\begin{theorem}{皮亚诺公理(G. Peano axioms)}{mapping}
(1) $0 \in \mathbf{N}$\\
(2) $x \in \mathbf{N} \to Sx \in \mathbf{N}$\\
(3) $x \in \mathbf{N} \to Sx \neq 0$\\
(4) $x \in \mathbf{N} \wedge y \in \mathbf{N} \wedge Sx =Sy \to x = y$\\
(5) $0 \in M \wedge \forall x (x\in M \to Sx\in M) \to \mathbf{N} \subseteq M$ for any property $M$ (axiom of induction).
	
\end{theorem}

\begin{note} 
	Cited from Encyclopedia of Mathematics \footnotemark. 
	A system of five axioms for the set of natural numbers $\mathbf{N}$ and a function $S$ (successor) on it, introduced by G. Peano (1889).
	In the first version of his system, Peano used 1
	instead of 0
	in axioms 1, 3, and 5. Similar axioms were proposed by R. Dedekind (1888).
\end{note}
\footnotetext{Peano axioms. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Peano\_axioms\&oldid=43518}
